home *** CD-ROM | disk | FTP | other *** search
/ The Programmer Disk / The Programmer Disk (Microforum).iso / xpro / pascal2 / pro12 / boyermo1.pas next >
Pascal/Delphi Source File  |  1988-01-23  |  13KB  |  224 lines
  1. { BOYERMO1.PAS ( 22 January 1988) (Rufus S. Hendon) }
  2.  
  3. {    This unit provides facilities for searching a text for a target using
  4.   the Boyer-Moore search method.  The routine is based on Don Strenczewilk's
  5.   implementation of a variant form of the Boyer-Moore method (his case-
  6.   insensitive version B1, available on CompuServe in file BLINE.ARC in
  7.   Borland BPROGA Data Library 4, uploaded 21 August 1987).  In addition to
  8.   repackaging his routine as a Turbo Pascal 4.0 unit, I have modified it
  9.   (1) to provide protection against endless loops that in the original
  10.   version can arise due to wrap-around of the index used to scan the text
  11.   when the length of the text approaches the maximum (65521 characters)
  12.   allowed by Turbo Pascal 4.0 for an array of type CHAR and (2) to improve
  13.   efficiency slightly by removing three instructions (a PUSH, a MOV, and a
  14.   POP) from the comparison loop.
  15.      The text to be searched must be stored in an array of type CHAR or an
  16.   equivalent user-defined type.  The lower bound of the array must be 1.
  17.   The target for which the text is to be searched must be of type STRING.
  18.      Whenever the text is to be searched for a new target, the program must
  19.   call MAKE_BOYER_MOORE_TABLE to have the shift table required by the Boyer-
  20.   Moore method created and to inform the unit of the target to be used when
  21.   the text is searched.  The function BOYER_MOORE_SEARCH searches the text
  22.   for the target specified in the most recent call to MAKE_BOYER_MOORE_TABLE,
  23.   beginning the search at a position in the text specified by the argument
  24.   associated with the parameter START.  To search the entire text, the
  25.   function would be invoked with START = 1.  The function scans the text
  26.   beginning from the START position for the first substring that matches the
  27.   target.  If such a substring is found, the function returns the position
  28.   (array subscript) of the initial character of the matching substring;
  29.   since the array is required to have 1 as its lower bound, the position
  30.   returned after a successful search will always be greater than 0.  If the
  31.   function fails to find a matching substring, it returns 0.
  32.      When it is required that all occurrences of the target in the text be
  33.   found, BOYER_MOORE_SEARCH would be invoked in a loop, in which the START
  34.   argument would initially have the value of 1; thereafter, after every
  35.   successful search, the START argument would be reset to the position
  36.   returned by the function plus 1.  The loop would terminate when the
  37.   function reported failure.  The loop would have a general structure
  38.   similar to this:
  39.  
  40.     item := [the target string];
  41.     make_Boyer_Moore_table(item);
  42.     scan_beginning := 1;
  43.     search_text_length := length(search_text);
  44.     repeat
  45.       i := Boyer_Moore_search(search_text,scan_beginning,search_text_length);
  46.       if i > 0 then begin
  47.         [do whatever processing is required when the search is successful];
  48.         scan_beginning := i+1
  49.       end
  50.     until i = 0
  51.  
  52.      Note that if the text array can only be referred to by means of a
  53.   pointer, as will be the case if the array is allocated in the heap by
  54.   means of the NEW procedure, the pointer, when used as the first argument
  55.   of BOYER_MOORE_SEARCH, must be dereferenced by writing '^' after it.  If,
  56.   for example, TEXTPTR is a pointer to the text array, the call to the
  57.   search function in the loop just given would take this form:
  58.  
  59.       i := Boyer_Moore_search(textptr^,scan_beginning,search_text_length);
  60.                                                                              }
  61. {============================================================================}
  62. unit BOYERMO1;
  63. {============================================================================}
  64. interface
  65.  
  66. procedure MAKE_BOYER_MOORE_TABLE(var target: string);
  67. { TARGET is the target string for which a text is to be searched.  A shift
  68.   table for the target string is constructed in private storage in the unit
  69.   and a copy of the target string is also stored inside the unit for
  70.   subsequent use by BOYER_MOORE_SEARCH. }
  71.  
  72. function BOYER_MOORE_SEARCH(var text_array; start, text_length: word):
  73.     word;
  74. { TEXT_ARRAY is an array of characters in which a text is stored; the
  75.   text begins in TEXT_ARRAY[1] and is TEXT_LENGTH characters long.  A
  76.   Boyer-Moore search is performed on the text in TEXT_ARRAY, beginning with
  77.   the character in position START, for the first substring that matches
  78.   the target string specified in the most recent invocation of
  79.   MAKE_BOYER_MOORE_TABLE.  If a match is found, the position of the first
  80.   character of the matching substring is returned.  Otherwise 0 is
  81.   returned. }
  82. {============================================================================}
  83. implementation
  84.  
  85. const
  86.   copy: string = '';  { initialized to an empty string to protect against }
  87.                       { the invocation of BOYER_MOORE_SEARCH without a    }
  88.                       { prior call to MAKE_BOYER_MOORE_TABLE              }
  89. var
  90.   table: array[char] of byte;
  91. {****************************************************************************}
  92. procedure MAKE_BOYER_MOORE_TABLE(var target: string);
  93. { TARGET is the target string for which a text is to be searched.  A shift
  94.   table for the target string is constructed in private storage in the unit
  95.   and a copy of the target string is also stored inside the unit for
  96.   subsequent use by BOYER_MOORE_SEARCH. }
  97. begin { MAKE_BOYER_MOORE_TABLE }
  98.   inline
  99.     ($1E/             {        push ds             }
  100.      $1E/             {        push ds             }
  101.      $07/             {        pop es              }
  102.      $BF/>copy/       {        mov di,offset copy  }
  103.      $C5/$76/<target/ {        lds si,[bp].target  }
  104.      $8B/$DE/         {        mov bx,si           }
  105.      $32/$E4/         {        xor ah,ah           }
  106.      $8A/$04/         {        mov al,[si]         }
  107.      $26/$88/$05/     {        mov es:[di],al      }
  108.      $FC/             {        cld                 }
  109.      $0A/$C0/         {        or al,al            }
  110.      $74/$06/         {        jz tbl              }
  111.      $46/             {        inc si              }
  112.      $47/             {        inc di              }
  113.      $8B/$C8/         {        mov cx,ax           }
  114.      $F3/$A4/         {        rep movsb           }
  115.      $BF/>table/      { tbl:   mov di,offset table }
  116.      $8B/$F3/         {        mov si,bx           }
  117.      $8B/$D7/         {        mov dx,di           }
  118.      $8A/$E0/         {        mov ah,al           }
  119.      $B9/>$0080/      {        mov cx,80h          }
  120.      $F3/$AB/         {        rep stosw           }
  121.      $8B/$F3/         {        mov si,bx           }
  122.      $8B/$FA/         {        mov di,dx           }
  123.      $46/             {        inc si              }
  124.      $98/             {        cbw                 }
  125.      $3C/$01/         {        cmp al,1            }
  126.      $7E/$13/         {        jle done            }
  127.      $48/             {        dec ax              }
  128.      $8A/$CC/         {        mov cl,ah           }
  129.      $8A/$FC/         {        mov bh,ah           }
  130.      $8A/$1C/         {  next: mov bl,[si]         }
  131.      $8B/$D0/         {        mov dx,ax           }
  132.      $2B/$D1/         {        sub dx,cx           }
  133.      $88/$11/         {        mov [bx+di],dl      }
  134.      $46/             {        inc si              }
  135.      $41/             {        inc cx              }
  136.      $3B/$C8/         {        cmp cx,ax           }
  137.      $75/$F2/         {        jne next            }
  138.      $1F)             {  done: pop ds              }
  139. end; { MAKE_BOYER_MOORE_TABLE }
  140. {****************************************************************************}
  141. function BOYER_MOORE_SEARCH(var text_array; start, text_length: word): word;
  142. { TEXT_ARRAY is an array of characters in which a text is stored; the
  143.   text begins in TEXT_ARRAY[1] and is TEXT_LENGTH characters long.  A
  144.   Boyer-Moore search is performed on the text in TEXT_ARRAY, beginning with
  145.   the character in position START, for the first substring that matches
  146.   the target string specified in the most recent invocation of
  147.   MAKE_BOYER_MOORE_TABLE.  If a match is found, the position of the first
  148.   character of the matching substring is returned.  Otherwise 0 is
  149.   returned. }
  150. begin { BOYER_MOORE_SEARCH }
  151.   inline
  152.     ($1E/                  {            push ds                 }
  153.      $33/$C0/              {            xor ax,ax               }
  154.      $8B/$D0/              {            mov dx,ax               }
  155.      $BE/>copy/            {            mov si,offset copy      }
  156.      $8A/$14/              {            mov dl,[si]             }
  157.      $80/$FA/$01/          {            cmp dl,1                }
  158.      $7F/$1F/              {            jg boyer                }
  159.      $7C/$6E/              {            jl notfound2            }
  160.      $8A/$44/$01/          {            mov al,[si+1]           }
  161.      $8B/$56/<start/       {            mov dx,[bp+start]       }
  162.      $4A/                  {            dec dx                  }
  163.      $8B/$4E/<text_length/ {            mov cx,[bp+text_length] }
  164.      $2B/$CA/              {            sub cx,dx               }
  165.      $C4/$7E/<text_array/  {            les di,[bp+text_array]  }
  166.      $8B/$DF/              {            mov bx,di               }
  167.      $03/$FA/              {            add di,dx               }
  168.      $FC/                  {            cld                     }
  169.      $F2/$AE/              {            repne scasb             }
  170.      $75/$56/              {            jne notfound2           }
  171.      $97/                  {            xchg ax,di              }
  172.      $2B/$C3/              {            sub ax,bx               }
  173.      $EB/$53/              {            jmp short exit          }
  174.      $FE/$CA/              { boyer:     dec dl                  }
  175.      $03/$F2/              {            add si,dx               }
  176.      $C4/$7E/<text_array/  {            les di,[bp+text_array]  }
  177.      $8B/$CF/              {            mov cx,di               }
  178.      $03/$4E/<text_length/ {            add cx,[bp+text_length] }
  179.      $49/                  {            dec cx                  }
  180.      $4F/                  {            dec di                  }
  181.      $03/$7E/<start/       {            add di,[bp+start]       }
  182.      $03/$FA/              {            add di,dx               }
  183.      $8A/$74/$01/          {            mov dh,[si+1]           }
  184.      $BB/>table/           {            mov bx,offset table     }
  185.      $55/                  {            push bp                 }
  186.      $8B/$E9/              {            mov bp,cx               }
  187.      $8A/$EC/              {            mov ch,ah               }
  188.      $FD/                  {            std                     }
  189.      $EB/$05/              {            jmp short comp          }
  190.      $D7/                  { nexttable: xlat                    }
  191.      $03/$F8/              {            add di,ax               }
  192.      $72/$2A/              {            jc notfound             }
  193.      $3B/$EF/              { comp:      cmp bp,di               }
  194.      $72/$26/              {            jb notfound             }
  195.      $26/$8A/$05/          {            mov al,es:[di]          }
  196.      $3A/$F0/              {            cmp dh,al               }
  197.      $75/$F0/              {            jne nexttable           }
  198.      $4F/                  {            dec di                  }
  199.      $8A/$CA/              {            mov cl,dl               }
  200.      $F3/$A6/              {            repe cmpsb              }
  201.      $74/$0D/              {            je found                }
  202.      $8A/$C2/              {            mov al,dl               }
  203.      $2B/$C1/              {            sub ax,cx               }
  204.      $03/$F8/              {            add di,ax               }
  205.      $47/                  {            inc di                  }
  206.      $03/$F0/              {            add si,ax               }
  207.      $8A/$C6/              {            mov al,dh               }
  208.      $EB/$DC/              {            jmp short nexttable     }
  209.      $5D/                  { found:     pop bp                  }
  210.      $C4/$46/<text_array/  {            les ax,[bp+text_array]  }
  211.      $97/                  {            xchg ax,di              }
  212.      $2B/$C7/              {            sub ax,di               }
  213.      $40/                  {            inc ax                  }
  214.      $40/                  {            inc ax                  }
  215.      $EB/$03/              {            jmp short exit          }
  216.      $5D/                  { notfound:  pop bp                  }
  217.      $32/$C0/              { notfound2: xor al,al               }
  218.      $89/$46/$FE/          { exit:      mov [bp-2],ax           }
  219.      $FC/                  {            cld                     }
  220.      $1F)                  {            pop ds                  }
  221. end; { BOYER_MOORE_SEARCH }
  222. {****************************************************************************}
  223. end.
  224.